package com.wzh.test;

import java.util.Stack;

/**
 * 写一个单向链表，功能
 * 1、插入水浒英雄排行榜
 * 2、打印
 * 3、修改
 * 4、删除
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        SingleLinkedList list = new SingleLinkedList();
        list.add(new Node(1, "宋江", "及时雨"));
        list.add(new Node(5, "公孙胜", "入云龙"));
        list.add(new Node(2, "卢俊义", "玉麒麟"));
        list.add(new Node(3, "吴用", "智多星"));
        list.add(new Node(4, "林冲", "豹子头"));
        list.show();

        list.modify(new Node(2, "小卢", "小玉"));
        System.out.println("===================================");
        list.show();

        list.del(2);
        System.out.println("===================================");
        list.show();

        int size = list.size();
        System.out.println("===================================");
        System.out.println("size=" + size);

//        System.out.println("================倒数第k个节点===================");
//        Node node = list.getBackNode(1);
//        System.out.println(node);

        //System.out.println("================reverse===================");
        //list.reverse();
        //list.show();

//        System.out.println("================reverse2===================");
//        list.reverse2();
//        list.show();


//        System.out.println("================reversePrint1===================");
//        list.reversePrint1();

//        System.out.println("================reversePrint2===================");
//        list.reversePrint2();

        SingleLinkedList list2 = new SingleLinkedList();
        list2.add(new Node(10, "宋江", "及时雨"));
        list2.add(new Node(50, "公孙胜", "入云龙"));
        list2.add(new Node(20, "卢俊义", "玉麒麟"));
        list2.add(new Node(30, "吴用", "智多星"));
        list2.add(new Node(40, "林冲", "豹子头"));

        merge(list,list2);
        System.out.println("===================================");
        list.show();



    }

    public static void merge(SingleLinkedList list1,SingleLinkedList list2){
        Node tempNode = list2.getFirst();
        while (tempNode != null){
            Node next = tempNode.getNext();
            list1.add(tempNode);
            tempNode = next;
        }
    }
}

class SingleLinkedList {
    private Node head;

    public SingleLinkedList() {
        this.head = new Node(0, "", "");
    }

    public Node getFirst() {
        return this.head.getNext();
    }

    public void add(Node node) {
        if (head.getNext() == null) {
            head.setNext(node);
            return;
        }

        Node tempNode = head;

        while (true) {
            if (tempNode.getNext() != null) {
                if (tempNode.getNext().getNo() > node.getNo()) {
                    node.setNext(tempNode.getNext());
                    tempNode.setNext(node);
                    break;
                } else {
                    tempNode = tempNode.getNext();
                }
            } else {
                tempNode.setNext(node);
                node.setNext(null);
                break;
            }
        }


    }

    public void show() {
        Node tempNode = head;
        boolean loop = true;
        while (loop) {
            if (tempNode.getNext() != null) {
                tempNode = tempNode.getNext();
                System.out.println(tempNode);
            } else {
                loop = false;
            }
        }
    }

    public void modify(Node node) {
        Node tempNode = head;
        while (true) {
            if (tempNode.getNext() != null) {
                tempNode = tempNode.getNext();
                if (tempNode.getNo() == node.getNo()) {
                    tempNode.setName(node.getName());
                    tempNode.setNickName(node.getNickName());
                    break;
                }
            } else {
                throw new RuntimeException("没有找到对应节点");
            }
        }
    }

    public void del(int no) {
        Node tempNode = head;
        while (true) {
            if (tempNode.getNext() != null) {
                if (tempNode.getNext().getNo() == no) {
                    tempNode.setNext(tempNode.getNext().getNext());
                    break;
                }
                tempNode = tempNode.getNext();
            } else {
                break;
            }
        }
    }

    public int size() {
        int count = 0;
        Node tempNode = head;
        while (true) {
            if (tempNode.getNext() != null) {
                count++;
                tempNode = tempNode.getNext();
            } else {
                break;
            }
        }
        return count;
    }

    public Node getBackNode(int k) {
        //首先计算节点数量size
        //倒数第k=正数size-k
        Node tempNode = head;
        if (tempNode.getNext() == null) {
            return null;
        }
        int size = size();
        int count = 0;
        int destCount = size - k + 1;
        while (true) {
            if (tempNode.getNext() != null) {
                count++;
                tempNode = tempNode.getNext();
            }
            if (count == destCount) {
                return tempNode;
            }
        }
    }

    public void reverse() {
        //借用数组实现
        int size = size();
        Node[] nodes = new Node[size];
        int index = 0;
        Node tempNode = head;
        while (true) {
            if (tempNode.getNext() != null) {
                tempNode = tempNode.getNext();
                nodes[index] = tempNode;
                index++;
            } else {
                break;
            }
        }
        head.setNext(nodes[size - 1]);
        for (int i = size - 1; i >= 1; i--) {
            nodes[i].setNext(nodes[i - 1]);
        }
        nodes[0].setNext(null);
    }

    public void reverse2() {
        //头插法实现链表反转
        Node newHead = new Node(-1, "", "");
        Node currentNode = head.getNext();
        while (true) {
            if (currentNode != null) {
                Node nextNode = currentNode.getNext();
                currentNode.setNext(newHead.getNext());
                newHead.setNext(currentNode);
                currentNode = nextNode;

            } else {
                break;
            }
        }
        head.setNext(newHead.getNext());
    }

    public void reversePrint1() {
        Node tempNode = head;
        if (tempNode.getNext() != null) {
            print1(tempNode.getNext());
        }
    }

    private void print1(Node node) {
        if (node.getNext() != null) {
            print1(node.getNext());
            System.out.println(node);
        } else {
            System.out.println(node);
        }
    }

    /**
     * 利用stack实现逆序打印
     */
    public void reversePrint2() {
        Stack stack = new Stack();
        Node currentNode = head.getNext();
        while (currentNode != null) {
            stack.add(currentNode);
            currentNode = currentNode.getNext();
        }
        //开始pop print
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }
}

class Node {
    private int no;
    private String name;
    private String nickName;
    private Node next;

    public Node(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getNickName() {
        return nickName;
    }

    public void setNickName(String nickName) {
        this.nickName = nickName;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}